package sword.chapter5HashMap;

import java.util.*;

/**
 * 变位词组
 * map key存质数乘积 value存同位词组
 * 方法1 将每个字母映射为质数，计算单词的质数乘积，map判断质数乘积
 *
 * map key存排序好的字符串 value存同位词组
 * 方法2 将每个单词排序，map判断排序好的字符串
 *
 * @author K
 * @date 2021-12-02 20:52
 */
public class S33GroupAnagrams {
    public static List<List<String>> s33(String[] strs) {
        int hash[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
                43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
        Map<Long, List<String>> groups = new HashMap<>();
        for (String str : strs) {
            long wordHash = 1;
            for (int i = 0; i < str.length(); i++) {
                wordHash *= hash[str.charAt(i) - 'a'];
            }
            groups.putIfAbsent(wordHash, new ArrayList<>());
            groups.get(wordHash).add(str);
        }

        return new ArrayList<>(groups.values());
    }

    public static List<List<String>> s33A(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sorted = new String(chars);
            groups.putIfAbsent(sorted, new ArrayList<>());
            groups.get(sorted).add(str);
        }

        return new ArrayList<>(groups.values());
    }

    public static void main(String[] args) {
        String[] strs = new String[]{"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> result = s33(strs);
        List<List<String>> result2 = s33A(strs);
        System.out.println();
    }

}
